package com.cat.dynamicPlanning;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/description/
 * @create 2025/8/27 17:23
 * @since JDK17
 */

public class Solution15 {
    public long maximumTotalDamage(int[] power) {
        TreeMap<Integer, Long> map = new TreeMap<>();
        for (int num : power) {
            map.merge(num, ((long) num), Long::sum);
        }
        List<List<Long>> list = new ArrayList<>();
        for (Map.Entry<Integer, Long> entry : map.entrySet()) {
            ArrayList<Long> t = new ArrayList<>();
            t.add(((long) entry.getKey()));
            t.add(entry.getValue());
            list.add(t);
        }
        long[] dp = new long[list.size() + 1];
        dp[0] = list.get(0).get(1);
        long ans = dp[0], a, b;
        for (int i = 1, j; i < list.size(); i++) {
            a = list.get(i).get(0);
            b = list.get(i).get(1);
            for (j = i - 1; j >= 0 && list.get(j).get(0) + 2 >= a; j--) {
                dp[i] = Math.max(dp[i], dp[j]);
            }
            if (j >= 0) {
                dp[i] = Math.max(dp[i], dp[j] + b);
            } else {
                dp[i] = Math.max(dp[i], b);
            }
            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}
